'''
思路:
    取一个元素p(第一个元素),使元素p归位;
    列表被p分为两个部分,左边都比p小,右边都比p大
    递归完成排序
快速排序的效率:
    时间复杂度 nlogn
快速排序的最坏情况: n^2

'''
def partition(li,left,right):
    tmp = li[left]
    while left < right:
        while left < right and li[right] >= tmp: # 从右边找比tmp小的数
            right -= 1  # 往左走一步
        li[left] = li[right]  # 把右边找到的值写到左边空位上
        while left < right and li[left] <= tmp:
            left += 1
        li[right] = li[left]   # 把左边找到的值写到刚才右边的地方
    li[left] = tmp # 把tmp归位
    return left

def quick_sort(li,left,right):
    if left < right: #至少两个元素
        mid = partition(li,left,right)
        quick_sort(li,left,mid-1)
        quick_sort(li,mid+1,right)
li = [5,7,4,6,3,1,2,9,8]
print(li)
quick_sort(li,0,len(li)-1)
print(li)